package algorithm.leetcode.I201to400;

import java.util.LinkedList;
import java.util.Queue;

public class Q225 {
}


class MyStack {

    Queue<Integer> mainQueue;
    Queue<Integer> minorQueue;

    /** Initialize your data structure here. */
    public MyStack() {
        mainQueue = new LinkedList<>();
        minorQueue = new LinkedList<>();
    }

    /** Push element x onto stack. */
    public void push(int x) {
        // 直接添加到main后面就可以
        mainQueue.add(x);

    }

    /** Removes the element on top of the stack and returns that element. */
    public int pop() {
        // 把main的全倒腾到minor里去(剩一个),这是公共动作1
        leaveOneInMain();
        // 把main剩下的这一个拿出来
        int popElement = mainQueue.poll();
        // 把刚刚倒腾到minor里的k-1个再全部倒腾回main里,这是公共动作2
        minor2Main();
        return popElement;
    }

    /** Get the top element. */
    public int top() {
        // 把main的全倒腾到minor里去(剩一个),这是公共动作1
        leaveOneInMain();
        // 把main剩下的这一个不拿出来
        int peekElement = mainQueue.poll();
        // 把剩下的这一个也倒腾到minor里
        minorQueue.add(peekElement);
        // 把刚刚倒腾到minor里的k-1个再全部倒腾回main里,这是公共动作2
        minor2Main();
        return peekElement;
    }

    /** Returns whether the stack is empty. */
    public boolean empty() {
        return mainQueue.isEmpty() && minorQueue.isEmpty();
    }

    private void leaveOneInMain() {
        while (mainQueue.size() > 1) {
            minorQueue.add(mainQueue.poll());
        }
    }

    private void minor2Main() {
        while (!minorQueue.isEmpty()) {
            mainQueue.add(minorQueue.poll());
        }
    }
}

/**
 * Your MyStack object will be instantiated and called as such:
 * MyStack obj = new MyStack();
 * obj.push(x);
 * int param_2 = obj.pop();
 * int param_3 = obj.top();
 * boolean param_4 = obj.empty();
 */